//
//  34. 在排序数组中查找元素的第一个和最后一个位置.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/5/20.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation

class Solution34 {
    // 简单看是一个二分查找
    // 但真正找出第一个出现的值，和最后一个出现的值相对是困难的
    // 注意了，市面上的写法都是简略后的写法，太难懂了。
    // 还是这样分开写，思路清晰,这就是完美的寻找左边界与右边界的写法。
    // 原创写法
    func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
        let first = findFirst(nums, target: target)
        let last = findLast(nums, target: target)
        if first <= last,
           first >= 0,
           last >= 0,
            last < nums.count,
            nums[first] == target,
            nums[last] == target
        {
            return [first, last]
        }
        return [-1, -1]
    }
    func findFirst(_ nums: [Int], target: Int) -> Int {
        var left = 0
        var right = nums.count - 1
        var ans = -1
        while left <= right {
            let mid = (left + right) / 2
            if nums[mid] < target {
                left = mid + 1
            } else if nums[mid] == target {
                // 如果找到了，先记录下来，继续在左边找
                right = mid - 1
                ans = mid
            } else {
                right = mid - 1
            }
        }
        return ans
    }
    func findLast(_ nums: [Int], target: Int) -> Int {
        var left = 0
        var right = nums.count - 1
        var ans = -1  // 这个的初始化容易出错
        while left <= right {
            let mid = (left + right) / 2
            if nums[mid] < target {
                left = mid + 1
            } else if nums[mid] == target {
                // 已经找到了，先记录下来，继续在右边找
                left = mid + 1
                ans = mid
            } else {
                right = mid - 1
            }
        }
        return ans
    }
    
    static func test(){
        let solution = Solution34()
//       let nums = [5,7,8,8,8,10]
        let nums = [5,7,7,8,8,10]
//        let nums = [1]
        let result = solution.searchRange(nums, 6)
        print(result)
    }
}
